#include <bits/stdc++.h>
using namespace std;
bool isValid(string s) {
    int balance = 0;
    for(char c : s) {
        if(c == '(') ++balance;
        if(c == ')') --balance;  
        if(balance < 0) return false;      
    }
    return balance == 0;
}
void dfs(string &brackets, int n, vector<string> &res) {
    if(n == brackets.size()) {
        if(isValid(brackets)) {
            res.push_back(brackets);
        }
        return ;
    }
    brackets += '(';
    dfs(brackets, n, res);
    brackets.pop_back();
    brackets += ')';
    dfs(brackets, n, res);
    brackets.pop_back();
}
vector<string> generateParenthesis(int n) {
    vector<string> res;
    string current;
    dfs(current, n * 2, res);
    return res;
}